Performance analysis for dynamic tree embedding in k-partite networks by a random walk
Identifieur interne : 00CB27 ( Main/Exploration ); précédent : 00CB26; suivant : 00CB28Performance analysis for dynamic tree embedding in k-partite networks by a random walk
Auteurs : H. Shen [Australie] ; K. Li [États-Unis] ; Y. Pan [États-Unis] ; G. H. Young [Hong Kong] ; S. Q. Zheng [États-Unis]Source :
- Journal of parallel and distributed computing [ 0743-7315 ] ; 1998.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
We study the problem of dynamic tree embedding in k-partite networks Gk and analyze the performance on interpartition load distribution of the embedding. We show that, for ring-connected Gk, if the embedding proceeds by taking a unidirectional random walk at a length randomly chosen from [0, Δ-1], where Δ is a multiple of k, the best-case performance is achievable at probability √2πke-k, which is much higher than the asymptotically zero probability at which the worst-case performance may appear. We also show that the same probabilities hold for fully connected Gk if the embedding proceeds by taking a random walk at a length randomly chosen from [2, ∞). When k = 2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have a 50% chance to achieve the best-case performance. We also analyze the performances for embedding in these networks in the expected case and observe the interesting fact that they match the performances in the best case when the network is k-partitionable into partitions of equal size.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 006607
- to stream PascalFrancis, to step Curation: 006A55
- to stream PascalFrancis, to step Checkpoint: 006306
- to stream Main, to step Merge: 00DB93
- to stream Main, to step Curation: 00CB27
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Performance analysis for dynamic tree embedding in k-partite networks by a random walk</title><author><name sortKey="Shen, H" sort="Shen, H" uniqKey="Shen H" first="H." last="Shen">H. Shen</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>School of Computing and Information Technology, Griffith University</s1><s2>Nathan, Queensland 4111</s2><s3>AUS</s3><sZ>1 aut.</sZ></inist:fA14><country>Australie</country><wicri:noRegion>Nathan, Queensland 4111</wicri:noRegion></affiliation></author><author><name sortKey="Li, K" sort="Li, K" uniqKey="Li K" first="K." last="Li">K. Li</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Mathematics and Computer Science, State University of New York</s1><s2>New Paltz, New York 12561-2499</s2><s3>USA</s3><sZ>2 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>New Paltz, New York 12561-2499</wicri:noRegion></affiliation></author><author><name sortKey="Pan, Y" sort="Pan, Y" uniqKey="Pan Y" first="Y." last="Pan">Y. Pan</name><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Department of Computer Science, University of Dayton</s1><s2>Dayton, Ohio 45469-2160</s2><s3>USA</s3><sZ>3 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>Dayton, Ohio 45469-2160</wicri:noRegion></affiliation></author><author><name sortKey="Young, G H" sort="Young, G H" uniqKey="Young G" first="G. H." last="Young">G. H. Young</name><affiliation wicri:level="4"><inist:fA14 i1="04"><s1>Department of Computer and Engineering, The Chinese University of Hong Kong</s1><s2>Shatin</s2><s3>HKG</s3><sZ>4 aut.</sZ></inist:fA14><country>Hong Kong</country><placeName><settlement type="city">Sha Tin</settlement></placeName><orgName type="university">Université chinoise de Hong Kong</orgName></affiliation></author><author><name sortKey="Zheng, S Q" sort="Zheng, S Q" uniqKey="Zheng S" first="S. Q." last="Zheng">S. Q. Zheng</name><affiliation wicri:level="1"><inist:fA14 i1="05"><s1>Department of Computer Science, Louisiana State University</s1><s2>Baton Rouge, Louisiana 70803-4020</s2><s3>USA</s3><sZ>5 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>Baton Rouge, Louisiana 70803-4020</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">98-0439980</idno><date when="1998">1998</date><idno type="stanalyst">PASCAL 98-0439980 INIST</idno><idno type="RBID">Pascal:98-0439980</idno><idno type="wicri:Area/PascalFrancis/Corpus">006607</idno><idno type="wicri:Area/PascalFrancis/Curation">006A55</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">006306</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">006306</idno><idno type="wicri:doubleKey">0743-7315:1998:Shen H:performance:analysis:for</idno><idno type="wicri:Area/Main/Merge">00DB93</idno><idno type="wicri:Area/Main/Curation">00CB27</idno><idno type="wicri:Area/Main/Exploration">00CB27</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Performance analysis for dynamic tree embedding in k-partite networks by a random walk</title><author><name sortKey="Shen, H" sort="Shen, H" uniqKey="Shen H" first="H." last="Shen">H. Shen</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>School of Computing and Information Technology, Griffith University</s1><s2>Nathan, Queensland 4111</s2><s3>AUS</s3><sZ>1 aut.</sZ></inist:fA14><country>Australie</country><wicri:noRegion>Nathan, Queensland 4111</wicri:noRegion></affiliation></author><author><name sortKey="Li, K" sort="Li, K" uniqKey="Li K" first="K." last="Li">K. Li</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Mathematics and Computer Science, State University of New York</s1><s2>New Paltz, New York 12561-2499</s2><s3>USA</s3><sZ>2 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>New Paltz, New York 12561-2499</wicri:noRegion></affiliation></author><author><name sortKey="Pan, Y" sort="Pan, Y" uniqKey="Pan Y" first="Y." last="Pan">Y. Pan</name><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>Department of Computer Science, University of Dayton</s1><s2>Dayton, Ohio 45469-2160</s2><s3>USA</s3><sZ>3 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>Dayton, Ohio 45469-2160</wicri:noRegion></affiliation></author><author><name sortKey="Young, G H" sort="Young, G H" uniqKey="Young G" first="G. H." last="Young">G. H. Young</name><affiliation wicri:level="4"><inist:fA14 i1="04"><s1>Department of Computer and Engineering, The Chinese University of Hong Kong</s1><s2>Shatin</s2><s3>HKG</s3><sZ>4 aut.</sZ></inist:fA14><country>Hong Kong</country><placeName><settlement type="city">Sha Tin</settlement></placeName><orgName type="university">Université chinoise de Hong Kong</orgName></affiliation></author><author><name sortKey="Zheng, S Q" sort="Zheng, S Q" uniqKey="Zheng S" first="S. Q." last="Zheng">S. Q. Zheng</name><affiliation wicri:level="1"><inist:fA14 i1="05"><s1>Department of Computer Science, Louisiana State University</s1><s2>Baton Rouge, Louisiana 70803-4020</s2><s3>USA</s3><sZ>5 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>Baton Rouge, Louisiana 70803-4020</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Journal of parallel and distributed computing</title><title level="j" type="abbreviated">J. parallel distrib. comput.</title><idno type="ISSN">0743-7315</idno><imprint><date when="1998">1998</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Journal of parallel and distributed computing</title><title level="j" type="abbreviated">J. parallel distrib. comput.</title><idno type="ISSN">0743-7315</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Bipartite graph</term><term>Computer network</term><term>Data structure</term><term>Distributed system</term><term>Dynamic conditions</term><term>Graph theory</term><term>Hypercube</term><term>Parallel algorithm</term><term>Parallel computation</term><term>System performance</term><term>Tree(graph)</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Système réparti</term><term>Calcul parallèle</term><term>Algorithme parallèle</term><term>Structure donnée</term><term>Arbre graphe</term><term>Théorie graphe</term><term>Hypercube</term><term>Graphe biparti</term><term>Réseau ordinateur</term><term>Régime dynamique</term><term>Performance système</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We study the problem of dynamic tree embedding in k-partite networks G<sup>k</sup> and analyze the performance on interpartition load distribution of the embedding. We show that, for ring-connected G<sup>k</sup>, if the embedding proceeds by taking a unidirectional random walk at a length randomly chosen from [0, Δ-1], where Δ is a multiple of k, the best-case performance is achievable at probability √2πke<sup>-k</sup>, which is much higher than the asymptotically zero probability at which the worst-case performance may appear. We also show that the same probabilities hold for fully connected G<sup>k</sup> if the embedding proceeds by taking a random walk at a length randomly chosen from [2, ∞). When k = 2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have a 50% chance to achieve the best-case performance. We also analyze the performances for embedding in these networks in the expected case and observe the interesting fact that they match the performances in the best case when the network is k-partitionable into partitions of equal size.</div></front></TEI><affiliations><list><country><li>Australie</li><li>Hong Kong</li><li>États-Unis</li></country><settlement><li>Sha Tin</li></settlement><orgName><li>Université chinoise de Hong Kong</li></orgName></list><tree><country name="Australie"><noRegion><name sortKey="Shen, H" sort="Shen, H" uniqKey="Shen H" first="H." last="Shen">H. Shen</name></noRegion></country><country name="États-Unis"><noRegion><name sortKey="Li, K" sort="Li, K" uniqKey="Li K" first="K." last="Li">K. Li</name></noRegion><name sortKey="Pan, Y" sort="Pan, Y" uniqKey="Pan Y" first="Y." last="Pan">Y. Pan</name><name sortKey="Zheng, S Q" sort="Zheng, S Q" uniqKey="Zheng S" first="S. Q." last="Zheng">S. Q. Zheng</name></country><country name="Hong Kong"><noRegion><name sortKey="Young, G H" sort="Young, G H" uniqKey="Young G" first="G. H." last="Young">G. H. Young</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00CB27 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00CB27 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:98-0439980
|texte= Performance analysis for dynamic tree embedding in k-partite networks by a random walk
}}
| This area was generated with Dilib version V0.6.33. |  |